package com.gorkr.labuladong.data_struct.graph;

import org.junit.jupiter.api.Test;

import java.util.Collections;
import java.util.LinkedList;

/**
 * @author gorkr
 * @date 2022/06/10 11:25
 **/
public class M210CourseScheduleII {


    private LinkedList[] graph;
    boolean[] visited;
    boolean[] onPath;  // 寻找环的关键
    boolean hasCycle = false;

    private LinkedList<Integer> order;

    private void buildGraph(int numCourses, int[][] prerequisites){
        graph = new LinkedList[numCourses];
//        for (LinkedList g:
//             graph) {
//            g = new LinkedList<Integer>();
//        }
        for (int i = 0; i < graph.length; i++) {
            graph[i] = new LinkedList<Integer>();
        }

        for (int i = 0; i < prerequisites.length; i++) {
            int from = prerequisites[i][1], to = prerequisites[i][0];
            graph[from].add(to);

        }
    }



    public int[] findOrder(int numCourses, int[][] prerequisites) {
        buildGraph(numCourses,prerequisites);
        visited = new boolean[numCourses];
        onPath = new boolean[numCourses];
        order = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            traverse(graph,i);
        }

        if(hasCycle){
            return new int[0];
        }
        Collections.reverse(order);
        return order.stream().mapToInt(Integer::valueOf).toArray();



    }

    private void traverse( LinkedList<Integer>[] graph, int s){
        if(onPath[s]){
            hasCycle = true;
            return;
        }
        if(visited[s] || hasCycle){
            return;
        }
        visited[s] = true;

        onPath[s] = true;
        for (int g :
                graph[s]) {
            traverse(graph, g);
        }
        onPath[s] = false;
        order.add(s);

    }



}
    